The present invention relates generally to routing data through a communication network, and more specifically to a system for calculating layered routes in a distributed manner.
In communication systems such as computer networks, routing is the process of determining the network links over which data, such as a packet or other type of data unit, is forwarded on its way through the network. Routing is performed by various kinds of data forwarding devices, sometimes referred to as routers and/or switches. A forwarding device that performs routing is typically connected to multiple communication links, and operates to select at least one of those communication links as an output link for each received data unit to be forwarded. The link or links over which data units are forwarded from one device to another is referred to as a “route” through a network. As it is generally known, network devices, including both forwarding devices and end stations, are referred to as the “nodes” of a network.
In various contexts, such as high speed networks using hop-by-hop flow control, or where cut-through routing is used, network operation using a given set of routes may create what is known as a “deadlock” condition. For example, deadlock can occur within a group of switches, each of which has buffers full of data, and cannot drop any packet from those buffers. Each of the switches in the group may be unable to forward its received data because the next switch to which the data must be forwarded also has no available buffers in which to store the data.
A number of existing systems have been developed to find deadlock-free sets of routes between all pairs of nodes in arbitrary network topologies. Examples of such existing systems have either constrained the topology of the network itself, and/or constrained the routes which may be taken through the network. For example, the topology of a network may be constrained such that the devices in the network are arranged as a grid. Given a grid topology, if all routes through the network are required to first traverse links horizontally as far as necessary, then vertically to the destination node, the network will be deadlock-free. Similarly, if a network topology is constrained to be a tree, which by definition includes no loops, that network will also be deadlock-free.
A well known approach to determining a deadlock-free set of routes through an arbitrary network topology is “up/down routing.” In up/down routing, one forwarding device in the network is chosen as the root node of a spanning tree for the network. All links within the network are then designated as “up” or “down” links with respect to the root node. The determination of an “up” or “down” state for a given link is based on the position of the link within the spanning tree. A link is “up” if it points from a lower to a higher level node in the tree. Otherwise, the link is considered a “down” link. For nodes at the same level, node IDs are used to break the tie. Routing of packets is performed such that any “up” links (towards the root) in the route are traversed before any “down” links are traversed (away from the root node) in order to reach the destination. Accordingly, once a “down” link has been traversed, no “up” links may subsequently be used within a route.
In many existing systems, a complete topology of the network is collected at a central node, and used to calculate a deadlock-free set of routes for the whole network. The deadlock-free set of routes is then used to generate a routing table at the central node, containing routing information that describes the set of routes. Once computed, the routing information in the routing table is distributed from the central system as forwarding tables to all other forwarding devices in the network, thus informing each forwarding device of the neighbor device to which each received data unit is to be forwarded, based on the destination of the received data unit.
A centralized approach to route generation is advantageous in that it allows a high degree of optimization, based on a global view of the network obtained by the central node. However, centralized generation of routes often does not scale well to large networks having many links and nodes. As the size of the network increases, so does the time required to obtain information at the central node, and the time required to distribute the generated routes throughout the network from the central node. Consequently, the time required to centrally generate and distribute a new set of routes for a very large network may be prohibitive for time-sensitive applications.
For these reasons it would be desirable to have a system for determining and providing routing information to devices in a network that does not require centralized route generation or distribution of routes from a central node. The system should provide routes that are deadlock-free, and that reflect some degree of cost optimization.